import hashlib


def hash(data_one, data_two):
    sha = hashlib.md5()
    sha.update("{0}{1}".format(data_one, data_two).encode("utf8"))
    return sha.hexdigest()


def merkle_tree(hash_data):
    """
    生成默克尔树
    :param hash_data: 原始交易信息
    :return: 默克尔树
    """
    hash_tree = {}
    count = 0
    hash_tree[str(count)] = hash_data
    while len(hash_data) != 1:
        hash_data_temp = []
        if len(hash_data) % 2 == 0:
            for i in range(0, int(len(hash_data) / 2) + 1, 2):
                hash_data_temp.append(hash(hash_data[i], hash_data[i + 1]))
        else:
            for i in range(0, int((len(hash_data) - 1) / 2) + 1, 2):
                hash_data_temp.append(hash(hash_data[i], hash_data[i + 1]))
            hash_data_temp.append(hash_data[len(hash_data) - 1])
        hash_data = hash_data_temp
        count = count + 1
        hash_tree[str(count)] = hash_data
    return hash_tree


if __name__ == '__main__':
    result = merkle_tree(['11111111111111111111111111', '01111111111111111111111111', '01111111111111111111111111','01111111111111111111111111'])
    print(result)
    print(len('658b925230da3d31e3daa6997bb5f20c'))